package com.frx.leetoffer.binarytree;

import java.util.Arrays;

/**
 * Created with IDEA
 *
 * @author: xrf
 * @Date: 2019/10/10
 * @Time: 10:29
 */
public class MinHeap {

    public int[] arr;

    public MinHeap(int[] arr){
        this.arr = arr;
        int startIndex = parent(arr.length -1);
        for (int i = startIndex; i>=0;i--){
            siftDown(i);
        }
    }

    public void add(int val){
        int size = arr.length;
        this.arr = Arrays.copyOf(arr,arr.length+1);
        arr[size] = val;
        siftUp(size);
    }

    public int remove(){
        int ret = arr[0];
        int last = arr[arr.length -1];
        int[] newArr = new int[arr.length -1];
        for (int i=0; i< arr.length-2;i++){
            newArr[i+1] = arr[i+1];
        }
        newArr[0] = last;
        this.arr = newArr;
        siftDown(0);
        return ret;
    }

    private int parent(int index){
        if (index == 0){
            throw new IllegalArgumentException("index 0 doesn't has parent ! ");
        }
        return (index -1)/2;
    }

    private int leftChild(int index){
        return 2 * index + 1;
    }

    /**
     * @description 堆的下沉
     * @param index
     */
    private void siftDown(int index){

        while (leftChild(index)< arr.length){
            int k = leftChild(index);
            if ((k+1) < arr.length && arr[k+1] < arr[k]){
                k = k+1;
            }
            if (arr[index] < arr[k]){
                break;
            }
            int temp = arr[index];
            arr[index] = arr[k];
            arr[k] = temp;
            index = k;
        }
    }

    /**
     * @description 堆的上浮
     * @param index
     */
    private void siftUp(int index){
        while (index > 0){
            int k = parent(index);
            if (arr[k] < arr[index]){
                break;
            }
            int temp = arr[k];
            arr[k] = arr[index];
            arr[index] = temp;
            index = k;
        }

    }

    /**
     * @description 堆排序
     */
    public void heapSort(){
        for (int i= arr.length -1;i>0;i--){
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            siftDown(0);
        }
    }

    public static void main(String[] args){
        int[] arr = {8,5,6,4,3,1,2};
        MinHeap heap = new MinHeap(arr);
        System.out.println(Arrays.toString(heap.arr));
/*        heap.add(0);
        System.out.println(Arrays.toString(heap.arr));
        System.out.println(heap.remove());
        System.out.println(Arrays.toString(heap.arr));*/
        // heap.heapSort();
        for (int i=0;i<arr.length-1;i++){
            arr[i] = heap.remove();
        }
        System.out.println(Arrays.toString(arr));
    }
}
